package leetcode.Hot100;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author Cheng Jun
 * Description: 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * <p>
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * 1 <= k <= nums.length <= 10^4
 * -10^4 <= nums[i] <= 10^4
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 * @version 1.0
 * @date 2021/12/4 22:29
 * @see topKFrequent
 * 面试题 经典题
 */
public class findKthLargest {

    // 时间复杂度 O(nlogn)
    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    // 模式识别：维护动态数据的最大最小值，可以考虑堆
    // 数据复杂度 O(nlogk)
    public static int findKthLargest1(int[] nums, int k) {
        PriorityQueue<Integer> numQ = new PriorityQueue<>();
        for (int num : nums) {
            numQ.add(num);
            if (numQ.size() > k) numQ.poll();
        }
        return numQ.peek();
    }
}
